A public key cipher (also called asymmetric cipher) is a cipher with two different keys: one for encryption and one for decryption. The encryption key is made public so anyone can use it, while the decryption key is kept secret. There are only a few public key ciphers known. Some known public key ciphers are RSA, Elliptic curves, McEliece, and Hidden Field Equations. When compared with symmetric ciphers, public key ciphers are relatively expensive in terms of, for instance, computing power, hardware cost, and/or time complexity. This makes current public key ciphers less useful for applications with cheap, resource-limited devices, such as sensors.
Niederreiter presented a variant of the McEliece encryption scheme that is based on linear error correcting codes. In Niederreiter's encryption scheme, a plain text message is interpreted as an error vector, and a ciphertext message is based on a syndrome of the error vector. Consequently, encryption may involve computing the syndrome of the error vector, and decryption may involve computing the error vector from the syndrome, in accordance with the particular error correcting code used. Because of the properties associated with error correcting codes, the error vectors can only have a limited number of ones. Consequently, the plaintext messages, which may have any number of ones, are first converted into error vectors with limited number of ones. This conversion step can take a considerable amount of computation time.